package newcoder;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author 肖地洋
 * @Date 2022/5/4 21:22
 */
public class NC221 {


    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    int[] nums;
    public ArrayList<ArrayList<Integer>> subsets (int[] nums) {
        // write code here
        ArrayList<Integer> list = new ArrayList<Integer>();
        Arrays.sort(nums);
        this.nums = nums;
        dfs(list,0);
        return res;
    }
    public void dfs(ArrayList<Integer> list,int index){
        res.add(new ArrayList<>(list));
        for(int i=index;i<nums.length;i++){
            // 剪枝
            if(i>index && nums[i] == nums[i-1])
                continue;
            list.add(nums[i]);
            dfs(list,i+1);
            list.remove(list.size()-1);
        }
    }

    public static void main(String[] args) {
        NC221 nc = new NC221();
        nc.subsets(new int[]{1,1,2});
    }
}
